package com.lft.ten_commonly_used_algorithms06.prim;

import java.util.Arrays;

/**
 * 普里姆算法
 */
public class PrimAlgorithm {
	public static void main(String[] args) {
		// 测试图
		char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		int numOfVertexs = data.length;
		// 邻接矩阵的关系使用二维数组表示，10000大数值，表示两个点不连通。
		int[][] edgesWeight = {
				{10000, 5, 7, 10000, 10000, 10000, 2},
				{5, 10000, 10000, 9, 10000, 10000, 3},
				{7, 10000, 10000, 10000, 8, 10000, 10000},
				{10000, 9, 10000, 10000, 10000, 4, 10000},
				{10000, 10000, 8, 10000, 10000, 5, 4},
				{10000, 10000, 10000, 4, 5, 10000, 6},
				{2, 3, 10000, 10000, 4, 6, 10000}
		};
		// 创建图对象。
		GraphAdjacencyMatrix graphAdjacencyMatrix = new GraphAdjacencyMatrix(numOfVertexs);
		// 创建一个MinTree对象
		MinimumCostSpanningTree minTree = new MinimumCostSpanningTree();
		// 生成图。
		minTree.createGraph(graphAdjacencyMatrix, numOfVertexs, data, edgesWeight);
		// 输出打印图。
		minTree.displayGraph(graphAdjacencyMatrix);
		// 测试 Prim 算法
		minTree.prim(graphAdjacencyMatrix, 0);
	}
}

/**
 * 创建最小生成树
 */
class MinimumCostSpanningTree {
	/**
	 * 创建图的邻接矩阵
	 * @param graphAdjacencyMatrix 图对象
	 * @param numOfVertexs         顶点数量
	 * @param data                 各顶点的数据
	 * @param edgesWeight          图的邻接（边的权重）
	 */
	public void createGraph(GraphAdjacencyMatrix graphAdjacencyMatrix, int numOfVertexs, char[] data, int[][] edgesWeight) {
		graphAdjacencyMatrix.numOfVertexes = numOfVertexs;
		int i = 0, j = 0;
		for (i = 0; i < numOfVertexs; i++) {
			graphAdjacencyMatrix.data[i] = data[i];
			for (j = 0; j < numOfVertexs; j++) {
				graphAdjacencyMatrix.edgesWeight[i][j] = edgesWeight[i][j];
			}
		}
	}
	
	/**
	 * 普里姆算法，得到取小生成树。
	 * @param graphAdjacencyMatrix 图对象
	 * @param vertexIndex          开始顶点的索引
	 */
	public void prim(GraphAdjacencyMatrix graphAdjacencyMatrix, int vertexIndex) {
		int numOfVertexes = graphAdjacencyMatrix.numOfVertexes;
		if (vertexIndex < 0 || vertexIndex >= numOfVertexes) {
			throw new ArrayIndexOutOfBoundsException();
		}
		// 访问标记，顶点是否被访问过。默认是false表示未被访问过。true 表示访问过。
		boolean[] visited = new boolean[numOfVertexes];
		
		// 把当前这个顶点标记为已访问。
		visited[vertexIndex] = true;
		// 用 h1 和 h2 记录顶点的下标。
		int h1 = -1;
		int h2 = -1;
		// 将 minWeight 初始化成一个最大值。后面的遍历过程中会寻找最小值。
		int minWeight = 10000;
		// 因为 N 个顶点，可以至少生成 N-1 条边。
		for (int k = 1; k < numOfVertexes; k++) {
			// 确定每次生成的子图，和哪个顶点最近。i 表示被访问过的。
			for (int i = 0; i < numOfVertexes; i++) {
				// j 表示 i 顶点能联通，但没被访问过的顶点。
				for (int j = 0; j < numOfVertexes; j++) {
					// 什么时候是访问过和未访问过。并且记录哪个节点离 i 最近。
					if (visited[i] && !visited[j] && graphAdjacencyMatrix.edgesWeight[i][j] < minWeight) {
						// 替换 minWeight 寻找 i 顶点 到未访问过的 j 顶点中路径最小的那个。
						minWeight = graphAdjacencyMatrix.edgesWeight[i][j];
						h1 = i;
						h2 = j;
					}
				}
			}
			// 这个循环结束就会找到一条最小的边。
			System.out.println("边 <" + graphAdjacencyMatrix.data[h1] + "," + graphAdjacencyMatrix.data[h2] + "> 的权值为: " + minWeight);
			// 将当前这个顶点标记为已经被访问过
			visited[h2] = true;
			// 再重置 minWeight 为最大值。给下次调用。
			minWeight = 10000;
		}
		
	}
	
	public void displayGraph(GraphAdjacencyMatrix graphAdjacencyMatrix) {
		for (int[] link : graphAdjacencyMatrix.edgesWeight) {
			System.out.println(Arrays.toString(link));
		}
	}
}

/**
 * 邻接矩阵——图
 */
class GraphAdjacencyMatrix {
	// 顶点数量
	int numOfVertexes;
	
	// 顶点数据
	char[] data;
	
	// 邻接矩阵，存放边的权值
	int[][] edgesWeight;
	
	public GraphAdjacencyMatrix(int numOfVertexes) {
		this.numOfVertexes = 0;
		this.data = new char[numOfVertexes];
		this.edgesWeight = new int[numOfVertexes][numOfVertexes];
	}
	
}